{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find All Duplicates in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDuplicates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中重复的数据"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>nums</code> ，其中 <code>nums</code> 的所有整数都在范围 <code>[1, n]</code> 内，且每个整数出现 <strong>一次</strong> 或 <strong>两次</strong> 。请你找出所有出现 <strong>两次</strong> 的整数，并以数组形式返回。</p>\n",
    "\n",
    "<p>你必须设计并实现一个时间复杂度为 <code>O(n)</code> 且仅使用常量额外空间的算法解决此问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,3,2,7,8,2,3,1]\n",
    "<strong>输出：</strong>[2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,2]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= n</code></li>\n",
    "\t<li><code>nums</code> 中的每个元素出现 <strong>一次</strong> 或 <strong>两次</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-all-duplicates-in-an-array](https://leetcode.cn/problems/find-all-duplicates-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-all-duplicates-in-an-array](https://leetcode.cn/problems/find-all-duplicates-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,2,7,8,2,3,1]', '[1,1,2]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        \n",
    "        for num in nums:\n",
    "            if nums[abs(num)-1] < 0:\n",
    "                res.append(abs(num))\n",
    "            else:\n",
    "                nums[abs(num)-1] *= -1\n",
    "        return res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: 'List[int]') -> 'List[int]':\n",
    "        duplicates_list = []\n",
    "        for i in range(len(nums)):\n",
    "            while nums[i] != i + 1:\n",
    "                to_idx = nums[i] - 1\n",
    "                if nums[i] == nums[to_idx]:\n",
    "                    duplicates_list.append(nums[i])\n",
    "                    break\n",
    "                nums[i] = nums[i] ^ nums[to_idx]\n",
    "                nums[to_idx] = nums[i] ^ nums[to_idx]\n",
    "                nums[i] = nums[i] ^ nums[to_idx]\n",
    "        return list(set(duplicates_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            orig = abs(nums[i])\n",
    "            if nums[orig - 1] < 0:\n",
    "                ans.append(orig)\n",
    "            nums[orig - 1] = -nums[orig - 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        output = []\n",
    "        for num in nums:\n",
    "            if nums[abs(num)-1] < 0:\n",
    "                output.append(abs(num))\n",
    "            else:\n",
    "                nums[abs(num)-1] *= -1\n",
    "        return output\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: 'List[int]') -> 'List[int]':\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        for i in nums:\n",
    "            index = abs(i)-1\n",
    "            if nums[index]<0:\n",
    "                res.append(index+1)\n",
    "            else:\n",
    "                nums[index]=-nums[index]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        \n",
    "        for x in nums:\n",
    "            if nums[abs(x)-1]<0:\n",
    "                res.append(abs(x))\n",
    "            else:\n",
    "                nums[abs(x)-1]*=-1\n",
    "                \n",
    "        return res\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        N = len(nums)\n",
    "        for i, n in enumerate(nums):\n",
    "            n %= N + 1\n",
    "            nums[n - 1] += N + 1\n",
    "        res = []\n",
    "        for i, v in enumerate(nums):\n",
    "            if v // (N + 1) == 2:\n",
    "                res.append(i + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        list1=[0]*(len(nums)+1)\n",
    "        for i in nums:\n",
    "            if list1[i]==0:\n",
    "                list1[i]=1\n",
    "            else:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        l = sorted(nums)\n",
    "        res = []\n",
    "        for i in range(len(l)-1):\n",
    "            if(l[i]==l[i+1]):\n",
    "                res.append(l[i])\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        res = []\n",
    "        pointer = 0\n",
    "        while pointer != len(nums):\n",
    "            if nums[pointer] == -1:\n",
    "                pointer += 1\n",
    "                continue\n",
    "            while nums[pointer] != nums[nums[pointer] - 1] and nums[nums[pointer] - 1] != -1:\n",
    "                temp = nums[nums[pointer] - 1]\n",
    "                nums[nums[pointer] - 1] = nums[pointer]\n",
    "                nums[pointer] = temp\n",
    "            if pointer != nums[pointer] - 1 and nums[nums[pointer] - 1] != -1:\n",
    "                res.append(nums[pointer])\n",
    "                nums[nums[pointer] - 1] = -1\n",
    "            pointer += 1\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        if len(nums) in (0,1):\n",
    "            return []\n",
    "        i = 0\n",
    "        while i <= len(nums)-1:\n",
    "            if i <= len(nums)-2:\n",
    "                if nums[i] == nums[i+1]:\n",
    "                    nums.pop(i)\n",
    "                    i +=1\n",
    "                elif nums[i] != nums[i+1]:\n",
    "                    nums.pop(i)\n",
    "            else:\n",
    "                nums.pop()\n",
    "        return nums\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            while nums[i] != 0 and nums[i]-1 != i:\n",
    "                if nums[nums[i]-1] == nums[i]:\n",
    "                    res.append(nums[i])\n",
    "                    nums[i] = 0\n",
    "                else:\n",
    "                    nums[nums[i]-1],nums[i] = nums[i],nums[nums[i]-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        length = len(nums)\n",
    "        i = 0\n",
    "        while i < length:\n",
    "            if nums[i] != nums[nums[i] - 1]:\n",
    "                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]\n",
    "            else:\n",
    "                i += 1\n",
    "        for i in range(0,length):\n",
    "            if nums[i] != i + 1:\n",
    "                ans.append(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        pos = 0\n",
    "        l = len(nums)\n",
    "        res = []\n",
    "        while pos < l:\n",
    "            #该位置已经是次数\n",
    "            if nums[pos] < 0:\n",
    "                pos = pos + 1\n",
    "                continue\n",
    "            val = nums[pos]\n",
    "            #val -1 位置已经是次数\n",
    "            if nums[val - 1] < 0:\n",
    "                if nums[val - 1] == -1:\n",
    "                    res.append(val)\n",
    "                nums[val - 1] -= 1\n",
    "                pos = pos + 1\n",
    "                continue\n",
    "            if pos != val - 1:\n",
    "                nums[pos] = nums[val - 1]\n",
    "                nums[val - 1] = -1\n",
    "            else:\n",
    "                nums[val - 1] = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        marker = [0 for _ in range(len(nums) + 1)]\n",
    "        result = []\n",
    "        for _ in nums:\n",
    "            marker[_] = marker[_] + 1\n",
    "        for _ in range((len(marker))):\n",
    "            if marker[_]>= 2:\n",
    "                result.append(_)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums):\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        res = []\n",
    "        while i < n:\n",
    "            if nums[i] != 0 and nums[i] -1 != i:\n",
    "                if nums[nums[i] - 1] == nums[i]:\n",
    "                    res.append(nums[i])\n",
    "                    nums[i] = 0\n",
    "                    i+=1\n",
    "                else:\n",
    "                    nums[nums[i] - 1],nums[i] = nums[i],nums[nums[i] - 1]\n",
    "            else:\n",
    "                i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        if not nums or len(nums)<2: return \n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        try:\n",
    "            while True:\n",
    "                if nums[i] != nums[i+1]:\n",
    "                    del nums[i]\n",
    "                else:\n",
    "                    i +=1\n",
    "        except:\n",
    "            del nums[-1]\n",
    "            return nums \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        o = len(nums)\n",
    "\n",
    "        y = 0\n",
    "        for i in range(o-1):\n",
    "            if nums[y] != nums[y + 1]:\n",
    "                nums.pop(y)\n",
    "            else:\n",
    "                y+=1\n",
    "        nums.pop(-1)\n",
    "        return nums\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        nums.sort()\n",
    "        if n == 2:\n",
    "            if nums[0] == nums[1]:\n",
    "                nums.pop(0)\n",
    "                return nums\n",
    "            else:\n",
    "                return []\n",
    "        while i<n-1:\n",
    "            if nums[i] != nums[i+1]:\n",
    "                nums.pop(i)\n",
    "                n = n-1\n",
    "            else:\n",
    "                nums.pop(i)\n",
    "                i+=1\n",
    "                n = n-1\n",
    "        if i == n-1:\n",
    "            nums.pop(i)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        i = 0\n",
    "        try:\n",
    "            while True:\n",
    "                if nums[i] != nums[i+1]:\n",
    "                    del nums[i]\n",
    "                else:\n",
    "                    i +=1\n",
    "        except:\n",
    "            del nums[-1]\n",
    "            return nums    # nums 进来， nums 返回  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        i = 0\n",
    "        while(i < len(nums)):\n",
    "            reIdx = nums[i] - 1\n",
    "            if(reIdx < 0):\n",
    "                i += 1\n",
    "            elif(nums[reIdx] > 0):\n",
    "                nums[i] = nums[reIdx]\n",
    "                nums[reIdx] = -1\n",
    "            else:\n",
    "                nums[reIdx] -= 1\n",
    "                nums[i] = 0\n",
    "        res = []\n",
    "        for idx, num in enumerate(nums):\n",
    "            if(num < -1):\n",
    "                res.append(idx + 1)\n",
    "        return res\n",
    "        # count = {}\n",
    "        # for num in nums:\n",
    "        #     if num in count.keys():\n",
    "        #         count[num] += 1\n",
    "        #     else:\n",
    "        #         count[num] = 1\n",
    "        # res = []\n",
    "        # for num in count.keys():\n",
    "        #     if(count[num] > 1):\n",
    "        #         res.append(num)\n",
    "        # return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\r\n",
    "        result = []\r\n",
    "        n = len(nums)\r\n",
    "        for i in range(n):\r\n",
    "            k = nums[i]\r\n",
    "            if k > 0:\r\n",
    "                nums[i] = 0\r\n",
    "            while k > 0:\r\n",
    "                if nums[k-1] < 0:\r\n",
    "                    nums[k-1] -= 1\r\n",
    "                    result.append(k)\r\n",
    "                    break\r\n",
    "                else:\r\n",
    "                    t = nums[k-1]\r\n",
    "                    nums[k-1] = -1\r\n",
    "                    k = t\r\n",
    "        result.sort()\r\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\r\n",
    "        st = 0\r\n",
    "        res = []\r\n",
    "        a = 0\r\n",
    "        while True:\r\n",
    "            head = True\r\n",
    "            while nums[a]>0:\r\n",
    "                print(a)\r\n",
    "                next = nums[a]-1\r\n",
    "                if head:\r\n",
    "                    nums[a] = 0\r\n",
    "                else:\r\n",
    "                    nums[a] = -1\r\n",
    "                a = next\r\n",
    "                head = False\r\n",
    "\r\n",
    "            if nums[a]<=0: \r\n",
    "                nums[a] -= 1\r\n",
    "\r\n",
    "            while st<len(nums) and nums[st]<=0:\r\n",
    "                st+=1\r\n",
    "            if st == len(nums): break\r\n",
    "            a = st\r\n",
    "            \r\n",
    "        # print(nums)\r\n",
    "        for i in range(len(nums)):\r\n",
    "            if nums[i]==-2:\r\n",
    "                res.append(i+1)\r\n",
    "        # print(res)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\r\n",
    "        st = 0\r\n",
    "        res = []\r\n",
    "        a = 0\r\n",
    "        while True:\r\n",
    "            head = True\r\n",
    "            while nums[a]>0:\r\n",
    "                print(a)\r\n",
    "                next = nums[a]-1\r\n",
    "                if head:\r\n",
    "                    nums[a] = 0\r\n",
    "                else:\r\n",
    "                    nums[a] = -1\r\n",
    "                a = next\r\n",
    "                head = False\r\n",
    "\r\n",
    "            if nums[a]<=0: \r\n",
    "                nums[a] -= 1\r\n",
    "\r\n",
    "            while st<len(nums) and nums[st]<=0:\r\n",
    "                st+=1\r\n",
    "            if st == len(nums): break\r\n",
    "            a = st\r\n",
    "            \r\n",
    "\r\n",
    "        print(nums)\r\n",
    "        for i in range(len(nums)):\r\n",
    "            if nums[i]==-2:\r\n",
    "                res.append(i+1)\r\n",
    "        print(res)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        ls = []\n",
    "        nums.sort()\n",
    "        while len(nums) > 1:\n",
    "            x = nums.pop()\n",
    "            if x == nums[-1] and x not in ls:\n",
    "                ls.append(x)\n",
    "        return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]:\n",
    "                cur = nums[i] - 1\n",
    "                nums[i] = -1\n",
    "                while nums[cur] > 0:\n",
    "                    temp = cur\n",
    "                    cur = nums[cur] - 1\n",
    "                    nums[temp] = 0\n",
    "                if not cur == i and nums[cur] == 0:\n",
    "                    res.append(cur + 1)\n",
    "                if nums[cur] == -1:\n",
    "                    nums[cur] = 0\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for num in nums:\n",
    "            x = (num-1)%n\n",
    "            nums[x]+=n\n",
    "        ans = [i+1 for i,v in enumerate(nums) if v > 2*n]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l = []\n",
    "        f, s = 1, 0\n",
    "        while f < n and s < n:\n",
    "            if nums[f] != nums[s]:\n",
    "                s += 1\n",
    "                nums[s] = nums[f]\n",
    "            else:\n",
    "                l.append(nums[s])\n",
    "            f += 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for x in nums.copy():\n",
    "            nums[x-1] = -1 if not nums[x-1] else 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == -1:\n",
    "                ans.append(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "不允许用o(n)级别的额外空间\n",
    "\n",
    "根据题目的数据范围，题解的方法是原地Hash\n",
    "\n",
    "\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        res = list()\n",
    "        for i in nums:\n",
    "            i_now = abs(i)\n",
    "            if nums[i_now - 1] < 0:\n",
    "                res.append(i_now)\n",
    "            \n",
    "            nums[i_now - 1] = 0 - nums[i_now - 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for x in nums:\n",
    "            x = abs(x)\n",
    "            if nums[x - 1] > 0:\n",
    "                nums[x - 1] = -nums[x - 1]\n",
    "            else:\n",
    "                ans.append(x)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        if not nums: return []\n",
    "        res=[]\n",
    "        n = len(nums)\n",
    "        # 1<=num<=n 遍历到 num 则令第 num 个元素变成-num\n",
    "        for i in range(n):\n",
    "            num=abs(nums[i])\n",
    "            # print(num,nums[num-1])\n",
    "            # 如果第num个数字已经是负的 说明之前遇到过num 说明num出现两次\n",
    "            if nums[num-1]<0:\n",
    "                res.append(num)\n",
    "            else:\n",
    "                nums[num-1]=-nums[num-1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "            nums.sort()\n",
    "            a = []\n",
    "            for i in range(1,len(nums)):\n",
    "                if nums[i-1] == nums[i]:\n",
    "                    a.append(nums[i])\n",
    "            return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            while nums[i] != nums[nums[i]-1]:\n",
    "                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]\n",
    "        print(nums)\n",
    "        return [num for i, num in enumerate(nums) if (num-1 != i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        hash=[0]*100001\n",
    "        for i in range(len(nums)):\n",
    "            hash[nums[i]]+=1\n",
    "        res=[]\n",
    "        for j in range(len(hash)):\n",
    "            if hash[j]>1:\n",
    "                res.append(j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        ans = set()\n",
    "        i = 0\n",
    "        for num in nums:\n",
    "            if num in ans:\n",
    "                nums[i] = num\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.add(num)\n",
    "        return nums[:i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        counter=dict()\n",
    "        for i in nums:\n",
    "            if i in counter:\n",
    "                counter[i]+=1\n",
    "            else:\n",
    "                counter[i]=1\n",
    "        res = []\n",
    "        for k,v in counter.items():\n",
    "            if v == 2:\n",
    "                res.append(k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        result = [k for k in cnt if cnt[k] == 2]  \n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
